Chihik's Blog

An Ac a day, keeps the doctor away!

P1587 [NOI2016]循环之美

发布于 2020-09-12 | 分类于 莫比乌斯反演 | 5分钟 | 764字数

类比十进制下的纯循环小数，kk 进制下的纯循环小数满足最简分数分母与 kk 互质。

而题目要求相同数值只计数一次，所以只需要考虑最简分数的情况。

那么答案为：

阅读全文 »

P2480 [SDOI2010]古代猪文

发布于 2020-09-12 | 分类于 数论 | 4分钟 | 515字数

g∑d∣nCnn/dmod  999911659g^{\sum_{d|n}C_{n}^{n/d}} \mod 999911659

g∑d∣nCndmod  999911659g^{\sum_{d|n}C_{n}^{d}} \mod 999911659

阅读全文 »

P3312 [SDOI2014]数表

发布于 2020-09-12 | 分类于 莫比乌斯反演 | 5分钟 | 758字数

∑i=1n∑j=1mσ((i,j))\sum_{i=1}^n\sum_{j=1}^m \sigma((i,j))

∑d=1min⁡(n,m)σ(d)∑i=1n∑j=1m[gcd(i,j)=d]\sum_{d=1}^{\min(n,m)}\sigma(d)\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=d]

阅读全文 »

P6055 [RC-02] GCD

发布于 2020-09-12 | 分类于 莫比乌斯反演 | 3分钟 | 471字数

这道题的反推还是挺有意思的。

∑i=1n∑j=1n∑p=1⌊nj⌋∑q=1⌊nj⌋[(i,j)=1][(p,q)=1]\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\lfloor \frac{n}{j} \rfloor}\sum_{q=1}^{\lfloor \frac{n}{j} \rfloor}[(i,j)=1][(p,q)=1]

阅读全文 »
0%